Les graphes

(Voici une solution possible au problème et voici comment j'ai corrigé vos travaux)

Un graphe est un ensemble de noeuds (normalement appelés sommets) qui sont reliés par des arêtes. Chaque sommet peut être le point de départ ou d'arrivée de tout nombre d'arêtes (il n'y a pas de maximum).

Un sommet peut contenir n'importe quelle information - l'exemple ici montre des sommets qui ne contiennent que des nombres entiers.

Un graphe peut être orienté ou non. Un graphe orienté a des flèches sur ses arêtes indiquant qu'il est possible de passer d'un sommet A à un sommet B, mais pas de B à A. Il est toutefois possible dans un graphe orienté de voir deux arêtes relier deux sommets, chacune dans un sens.

Une arête peut également avoir un coût, c'est à dire un nombre associé à l'arête (et non à un des sommets). Ce coût peut représenter un coût monétaire, une distance ou n'importe quel autre concept selon le graphe. Lorsqu'une arête a un coût, il faut "payer" ce coût pour passer d'un sommet à l'autre.

Un graphe peut être utilisé pour représenter n'importe quelle situation de la vie courante dans laquelle on doit passer par plusieurs étapes pour atteindre un but. Les sommets peuvent représenter les pièces d'une maison (ou d'un donjon!), les coins de rues dans une ville, des ordinateurs sur un réseau, des personnes dans un entourage ou des décisions dans un algorithme.

Les graphes sont couramment utilisés en recherche opérationnelle. La recherche opérationnelle est la science qui s'occupe de trouver des solutions à des problèmes combinatoires (des problèmes comprenant un grand nombre de solutions possibles et pour laquelle on cherchera la solution optimale) ou d'autres genres de problèmes similaires.

Le problème du plus court chemin

Un problème classique lorsque l'on implémente des graphes est de trouver le plus court chemin entre deux sommets donnés. Le problème est beaucoup plus intéressant lorsque l'on utilise un graphe où les arêtes ont des coûts.

Il existe beaucoup d'algorithmes pour trouver le plus court chemin dans un graphe. Le plus connu est probablement celui de Dijkstra (ça se prononce comme "Déïkstra"), algorithme nommé en l'honneur de son créateur, Edsger Wybe Dijkstra. C'est un algorithme qui garantit de trouver le plus court chemin possible en ne considérant jamais le même sommet deux fois.

Votre travail pour ce labo

Vous devrez produire tout d'abord une classe Sommet, un classe Arête et une classe Graphe qui permettent de représenter des graphes en mémoire. Ces graphes ne seront pas orientés (donc toute arête est traversable dans les deux directions) et chaque arête aura un coût entier associé. Les sommets ne contiendront qu'un simple numéro qui permettra de les identifier.

Vous devrez également intégrer une méthode Dijkstra à votre classe Graphe - cette méthode permettra soit de trouver le plus court chemin entre deux sommets, ou le plus court chemin entre un sommet de départ et tous les autres sommets du graphes (au choix de l'utilisateur).

Vous devrez respecter les spécifications suivantes à la lettre pour éviter de perdre des points:

La classe Sommet

Le Sommet est la base du Graphe puisque le Graphe contiendra un tableau de Sommets. Tout ce qu'on a besoin d'y stocker pour qu'un sommet puisse exister, c'est un numéro d'identification, mais vous aurez besoin d'ajouter quelques attributs supplémentaires pour que votre méthode Dijkstra puisse fonctionner plus facilement.

• Des attributs privés pour y stocker
  • Un numéro d'identification (int)
  • Tout autre attribut pertinent servant à faire fonctionner efficacement votre méthode Dijkstra
• Des propriétés publiques pour accéder à chacun des attributs: Numéro, puis les autres attributs que vous aurez décidé d'utiliser.
• Des constructeurs permettant de construire un sommet nul, un sommet avec un numéro et tout autre constructeur facilitant votre utilisation de la méthode Dijkstra.
• Un override de ToString retournant le numéro du sommet.

La classe Arête

On ne stockera pas d'Arêtes directement dans le graphe, mais les Arêtes pourront être utilisées comme "enrobage" pour passer de l'information entre le graphe et l'utilisateur.

• Des attributs privés pour y stocker:
  • Des pointeurs vers un sommet de départ et un sommet de fin
  • Une distance entière (la distance entre ces deux sommets)
• Des propriétés publiques pour accéder à chacun des attributs: Départ, Fin et Distance.
• Un constructeur permettant de construire une arête avec les trois attributs.

La classe Graphe

Il existe bien des façons d'implémenter un graphe en mémoire. Nous opterons ici pour une des solutions populaires et efficaces: un tableau de sommets et une matrice de coûts à deux dimensions (représentant en fin de compte les arêtes) qui indiquera le coût à payer pour passer d'un sommet à un autre.

Le graphe contiendra donc:

• Des attributs privés pour stocker:
  • Un tableau de Sommets
  • Un tableau à deux dimensions de distances (des entiers)
  • Un compteur de sommets (entier) - bien qu'on puisse s'en passer, c'est toujours utile.
  • Des pointeurs vers un sommet de départ et un sommet de fin (pouvant être utilisés par Dijkstra)
• Des propriétés publiques pour accéder à chacun des attributs: Sommets, Distances, NbSommets, Départ et Fin.
• Une propriété publique statique en lecture seule permettant d'obtenir la valeur "Infini" (qui sera représentée par 2147483647, le plus grand nombre à pouvoir tenir dans un int). Deux sommets qui ne sont pas reliés par une arête auront une distance infinie entre eux, nous assurant ainsi que Dijkstra ne voudra jamais passer par des arêtes inexistantes (mettre 0 comme distance rendrait ce chemin peu coûteux fort invitant!).
• Un constructeur acceptant le nombre de sommets du graphe (ce constructeur instanciera le tableau de sommets (et tous les sommets qui s'y trouveront) en plus d'initialiser le tableau de distances - au départ tous les sommets sont indépendants donc aucun d'eux n'est connecté à aucun autre).
• Des itérateurs (le premier est là juste question de faire standard, les autres seront utiles pour Dijkstra):
  • Le GetEnumerator() qui retourne tous les sommets du graphe
  • Un itérateur nommé NonVisités retournant tous les sommets qui n'ont pas encore été visités par Dijkstra (au départ il donne la même chose que le premier)
  • Un itérateur nommé Voisins qui accepte un sommet en paramètre et qui retourne une Arête pour chacun de ses sommets voisins (permettant ainsi à l'utilisateur d'obtenir non seulement tous les voisins d'un sommet, mais aussi les distances qui les séparent).
• Des méthodes permettant d'ajouter et d'enlever des arêtes au graphe. On sait que le graphe ne contient pas réellement d'arêtes, mais on peut le simuler pour l'utilisateur. On voudra donc pouvoir faire:
  • AjouterArête(int sommet1, int sommet2, int distance) - le graphe sera ajusté en conséquence (n'oubliez pas que nos graphes ne sont pas orientés!)
  • AjouterArête(Arête a) - le graphe sera aussi ajusté en conséquence, mais l'utilisateur pourra passer une Arête contenant toutes les informations utiles s'il le désire.
  • EnleverArête(int sommet1, int sommet2) - on enlève l'arête entre ces deux sommets (n'oubliez pas encore une fois que le graphe n'est pas orienté)
  • EnleverArête(Arête a) - même principe mais avec une Arête.

  Notons qu'on ne voudra pas modifier le nombre de sommets d'un graphe - on définira ce nombre à la construction et on n'enlèvera ni n'ajoutera jamais de sommets. Ceci nous permettra de garder nos classes simples et d'éviter de la manipulation de tableaux souvent fort coûteuse (si jamais on prévoyait que le nombre de sommets d'un graphe risquait de changer couramment lors d'une exécution, il serait plus sage d'implémenter notre graphe comme une liste de sommets, chacun contenant une liste de pointeurs vers ses voisins).

   

• Une méthode void Dijkstra(Sommet départ, Sommet cible) qui calculera les plus courts chemins:
• Si départ est null, Dijkstra utilisera le Départ du Graphe (c'est un attribut). Si le Départ du Graphe est aussi null, Dijkstra affichera un message d'erreur et ne fera rien.
• Si cible est null, Dijkstra calculera le plus court chemin pour tous les sommets du graphe, partant du sommet de départ.
• Si cible est définie, Dijkstra calculera le plus court chemin entre départ et cible.

Tout ceci nous permettra de définir aisément un graphe comme ceci:

en faisant quelque chose comme:

Graphe g = new Graphe(6);

g.AjouterArête(0, 1, 15);
g.AjouterArête(0, 2, 1);
g.AjouterArête(2, 3, 7);
g.AjouterArête(3, 1, 5);
g.AjouterArête(0, 4, 10);
g.AjouterArête(4, 1, 1);
g.AjouterArête(2, 5, 2);
g.AjouterArête(5, 3, 2);

g.Départ = g.Sommets[0];
g.Fin = g.Sommets[1];

Évidemment, les sommets sont numérotés à partir de 0.

L'algorithme de Dijkstra

L'algorithme de Dijkstra n'est pas compliqué. Chaque sommet doit pouvoir contenir un nombre représentant sa distance totale du sommet de départ et un pointeur vers le sommet précédent dans l'itinéraire trouvé jusqu'à présent. On modifiera ces valeurs tout au long de notre recherche. En effet, on trouvera le chemin le plus court en partant du point de départ et en explorant dans toutes les directions, privilégiant à chaque étape le chemin le moins coûteux jusqu'à présent. Lorsqu'on atteindra la cible voulue, on n'aura qu'à revenir en arrière en suivant les pointeurs vers le sommet précédent jusqu'au point de départ.

Au départ, tous les noeuds sont à une distance infinie du sommet de départ (donc non déterminée), sauf le sommet de départ qui est à une distance de 0 (bien sûr). Lorsque l'on parlera de la "distance" d'un sommet, cela signifiera "sa distance du sommet de départ tel que calculée jusqu'à maintenant".

L'algorithme sélectionnera le sommet ayant la plus petite distance parmi tous les sommets qu'il n'a pas encore sélectionnés (la première fois, ce sera nécessairement le sommet de départ). Ce sommet sera appelé le sommet courant.

On trouvera ensuite tous les voisins du sommet courant. Pour chaque voisin, si la distance du sommet courant + le coût de l'arête entre le sommet courant et le sommet voisin est plus petite que la distance du voisin, cela signifie qu'on a trouvé un chemin moins coûteux pour atteindre ce sommet voisin. Dans ce cas on modifiera la distance du voisin pour la mettre égale à celle du sommet courant + le coût de l'arête jusqu'au voisin, puis on fera pointer le pointeur "précédent" du voisin vers le sommet courant, nous permettant ainsi de revenir en arrière jusqu'au point de départ.

Une fois qu'on a ainsi traité tous les voisins du sommet courant, on recommence l'algorithme, sélectionnant le sommet qui a la distance la plus petite parmi tout ceux qui n'ont pas encore été sélectionnés.

Si on veut atteindre une cible en particulier, on peut arrêter lorsque le sommet courant est égal à cette cible. En effet, une fois qu'on en est là, tout calcul supplémentaire ne ferait que nous éloigner de la cible et tout autre sommet qui n'a jamais été sélectionné encore a une distance plus grande que la cible (et donc ne pourra jamais nous faire atteindre la cible par un chemin plus court). Si on veut calculer les distances pour tous les sommets du graphe, on continuera jusqu'à ce qu'il n'y ait plus de sommets qui n'ont jamais été sélectionnés.

Retrouver notre chemin

Une fois que Dijkstra a terminé sa magie, on peut partir de la cible (ou de n'importe quel sommet si on a calculé tout le graphe) et suivre les pointeurs précédents pour trouver le chemin de la cible au point de départ. Une bonne façon de les inverser afin d'avoir un chemin à l'endroit est de les pousser sur une pile puis de les "dépiler".

On peut faire par exemple:

g.Dijkstra(null,g.Fin);  // Ceci trouve le plus court chemin entre le point
  // de départ du graphe jusqu'au point final du graphe.
  
Stack<Sommet> pile = new Stack<Sommet>();  // On instancie une pile de Sommets
Sommet unSommet = g.Fin; // On part de la fin
Console.WriteLine("Meilleur chemin de {0} à {1}: longueur {2}", g.Départ, g.Fin, unSommet.Distance);

while (unSommet != null)
{
   pile.Push(unSommet);  // On empile chaque sommet
   unSommet = unSommet.Précédent; // puis on recule
} // jusqu'à ce qu'il n'y ait plus de précédent (donc au point de départ)

// Un foreach d'une pile énumère la pile de haut en bas sans en modifier le contenu
foreach (Sommet ss in pile)
   Console.WriteLine("{0} (distance {1})", ss.Numéro, ss.Distance);

La remise

Comme ce travail est lui aussi d'envergure, vous aurez deux semaines pour y travailler. Vous devrez donc remettre par courriel à votre charmant professeur un fichier .cs contenant vos classes Arête, Sommet et Graphe, sans Main. Ne faites pas de copier/coller de texte. Votre courriel doit me parvenir au plus tard vendredi le 2 novembre à 13h30. La période de laboratoire du 26 octobre sera également consacrée à ce travail.

Je vous conseille de commencer par faire les Arêtes, Sommets et Graphes sans vous soucier de Dijkstra. Lorsque vous pourrez représenter un graphe correctement en mémoire, attaquez-vous à la méthode Dijkstra (qui vous demandera de faire quelques ajouts à vos classes). Je couvrirai Dijkstra un peu plus en détail mercredi prochain.

Et maintenant: graphologues amateurs, à vos claviers!

 

Etienne Forest, 19 octobre 2007